package com.Astart 
{
	/**
	 * ...
	 * @author weoweo
	 */
	import flash.utils.getTimer;
	public class Astart 
	{
		
		private static var  _instance:Astart;
		public static var ProfectPath:Boolean = false;
		public function Astart(s:Single) 
		{
			
		}
		public static function findPath(grid:Grid):Array {
			
			if (grid == null || grid.startNode == null || grid.endNode == null) return null;
			
			if (_instance == null) _instance = new Astart( new Single());
				
			return _instance.hasPath(grid);
			
		}
		public static function get _visited():Array {
			if (_instance) return _instance._visited;
			return null;
		}
		public static function get cool ():Array {
			if (_instance) return _instance.cool;
			return null;
		}
		
		private var _arrange:Arrange;
		public var _visited:Array;
		private var _findFun:Function;
		private var _endNode:Node;
		private var _startNode:Node;
		public static var _vistedNum:uint = 0;
		private var _grid:Grid;
		private var _version:int = 0;
		private  function hasPath(grid:Grid):Array {
			
			var stime:uint = getTimer();
			_vistedNum = 0;
			_visited = [];
			_arrange = new Arrange();
			_arrange.key = "h";
		
			_findFun = euclidian;
			
			
			_startNode= grid.startNode as Node;
			_endNode = grid.endNode as Node;
			var node:Node = _startNode;
			node.f = 0; node.g = node.h = 0;
			
			var maxX:int = grid.row-1;
			var maxY:int = grid.col-1;
			var nodes:Array = grid.nodes as Array;
			
			var acount:uint = 0;
			var bcount:uint = 0;
			var ccount:uint = 0;
			while (node != _endNode) {
				
				var startX:int = node.x - 1; var endX:int = node.x + 1;
				var startY:int = node.y - 1; var endY:int = node.y + 1;
				if (startX < 0) startX = 0;
				if (endX > maxX) endX = maxX;
				if (startY < 0) startY = 0;
				if (endY > maxY) endY = maxY;
				
				/*
				trace("x " + node.x +" y " + node.y);
				trace("startx " + startX +" endx " + endX);
				trace("starty " + startY + " endy " + endY)
				trace("maxX " + maxX +" maxy " + maxY);
				 */
				
				for (var i:int = startX; i <= endX; i++ ) {
					
					for (var s:int = startY; s <= endY; s++ ) {
						_vistedNum++;
						var test:Node = nodes[s][i] as Node;
						if (test == null || !test.walkAble || test == node) continue;
						
						var four:Boolean = !(test.x == node.x || test.y == node.y)
						if (four) {
							var ynode:Node = nodes[test.y][node.x];
							var xnode:Node = nodes[node.y][test.x];
							if (ynode.walkAble==false&& xnode.walkAble==false) continue;
						}
						//acount++;
						var cost:Number = four?1.4:1.0;
						
						var _f:Number = node.f + cost;
						if (test.visited) {
							bcount++;
							if (test.f > _f) {
								test.f =_f;
								test.h = test.f + test.g;
								test.parent = node;
							}
							
						}else {
							ccount++;
							test.visited = true;
							test.f =_f;
							test.g = _findFun(test);
							test.h = test.f + test.g;
							test.parent = node;
							_arrange.put(test);
							//_visited.push(test);
						}
							
					}
				}

				node = _arrange.pop() as Node;
			
				if (node == null) return null;
				
				
			}
			
			
			var reArr:Array = [];
			while ( node!=_startNode) {
				reArr.unshift(node);
				node = node.parent as Node;
			}
			reArr.unshift(node);
			
			var utime:uint = getTimer() - stime;
		//	trace("总共循环次数: " + _vistedNum + "实际计算次数: " + acount + "\n" + " 重复访问的网格数: " + bcount + "代价函数调用次数: " + ccount + "\n" + "总耗时: " + utime);
			if (ProfectPath) reArr=profect(reArr);
			return reArr;

		}
		private function profect(arr:Array):Array {
			
			if (arr == null || arr.length < 3) return arr;
			var clean:Array = [];
			var node:Node = arr[0];
			var currentFace:int = getface(arr[1]);
			var endP:Node;
			var face:int;
			var test:Node;
			clean.push(node);
			var num:int;
			var oldTimer:uint = getTimer();
			for (var i:int = 1; i < arr.length; i++ ) {
				test = arr[i];
				face = getface(test);
				if (face != currentFace) {
					num++;
					if (endP) clean.push(endP);
					//clean.push(test);
					endP = test;
					currentFace = face;
				}else {
					endP = test;
					
				}
				node = test;
			}
			clean.push(endP);
			//trace("GGGGGGGGGGGGGGGGGGGGGGGGG "+clean.length+"  "+arr.length+"   "+num);
			//trace("use times "+(getTimer()-oldTimer));
			function getface(n:Node):int {
				//var result:int=(n.y - node.y) * 10 + (n.x - node.x);
				return (n.y - node.y) * 10 + (n.x - node.x);
			}
			return clean;
		}
	
		public  var cool:Array = [];

		private  var sqrt_2:Number = Math.SQRT2;
		private  function euclidian(s:Node):Number {
			
			 var disX:int = _endNode.x- s.x;
			var disY:int = _endNode.y - s.y;
			 return (disX * disX + disY * disY);
			
		}
		private  function diagonal(s:Node):Number {
			
			var disX:int = _endNode.x - s.x;
			var disY:int = _endNode.y - s.y;
			if (disX < 0) disX *= -1;
			if (disY < 0) disY *= -1;
			var min:int = disX < disY?disX:disY;
			return  min*sqrt_2 + (disX+disY - 2*min);
			
		}
		private  function  manhattan (s:Node):int {
			
			var disX:int = _endNode.x - s.x;
			var disY:int = _endNode.y - s.y;
			if (disX < 0) disX *= -1;
			if (disY < 0) disY *= -1;
			return disX + disY;
		}

	
	}

}
class Single { };